class LFUCache {
  constructor(capacity = 2) {
    const keyToVal = new Map()
    const keyToFreg = new Map()
    const fregToKeys = new Map()
    const increaseFreq = (key) => {
      let freg = keyToFreg.get(key)
      keyToFreg.set(key, freg + 1)
      fregToKeys.get(freg).delete(key)
      if (fregToKeys.has(freg + 1)) {
        fregToKeys.get(freg + 1).add(key)
      } else {
        fregToKeys.set(freg + 1, new Set([key]))
      }

      if (fregToKeys.get(freg).size === 0) {
        fregToKeys.delete(freg)
        if (freg === this.minFreq) {
          this.minFreq++
        }
      }
    }
    const removeMinFreqKey = () => {
      const keys = fregToKeys.get(this.minFreq)
      console.log('LFUCache -> removeMinFreqKey -> keys', this.minFreq, fregToKeys)
      const deleteKey = keys.values().next().value
      keys.delete(deleteKey)
      if (keys.size === 0) {
        fregToKeys.delete(this.minFreq)
      }
      keyToVal.delete(deleteKey)
      keyToFreg.delete(deleteKey)
    }
    this.capacity = capacity
    this.minFreq = 0
    this.get = (key) => {
      if (!keyToVal.has(key)) {
        return -1
      }
      increaseFreq(key)
      return keyToVal.get(key)
    }
    this.put = (key, val) => {
      if (this.capacity <= 0) return

      if (keyToVal.has(key)) {
        keyToVal.set(key, val)
        increaseFreq(key)
        return
      }

      if (this.capacity <= keyToVal.size) {
        removeMinFreqKey()
      }

      keyToVal.set(key, val)
      keyToFreg.set(key, 1)
      if (fregToKeys.has(1)) {
        fregToKeys.get(1).add(key)
      } else {
        fregToKeys.set(1, new Set([key]))
      }
      this.minFreq = 1
    }
    this.info = () => {
      console.log(keyToVal, keyToFreg, fregToKeys)
    }
  }
}

const lfu = new LFUCache()

lfu.put('a', 1)
console.log(lfu.get('a'))
lfu.put('b', 2)
console.log(lfu.get('b'))
lfu.put('c', 3)
lfu.put('d', 4)
lfu.info()